/**
 * Project: Useful Programs <br>
 * Package: other.dfa
 */
package org.leumasjaffe.math.dfa;

import java.util.HashMap;
import java.util.Set;

import org.eclipse.jdt.annotation.NonNullByDefault;
import org.eclipse.jdt.annotation.Nullable;

/**
 * Class .NFA in file NFA.java <br>
 * 
 * @author leumasjaffe
 * Created on: Sep 3, 2012
 * 
 */
@NonNullByDefault
public class NFA {
	final int Q;
	final int Sigma;
	final int[][][] Delta;
	final int[] S;
	final int[] F;
	
	private @Nullable DFA dfaConversion;
	
	private int numFinal = 0;
		
	public NFA(int numStates, int alphabet, int[][][] Delta, int[] startStates, int[] finalStates) {
		this.Q = numStates;
		this.Sigma = alphabet;
		this.Delta = Delta;
		this.S = startStates;
		this.F = finalStates;
	}

	
	@SuppressWarnings("null")
	public int[] Delta(int q, int a) {
		return this.Delta[q][a];
	}
	
	public boolean accepts(int[] x) {
		int[] out = Deltax(x);
		for (int f : this.F)
			for (int q : out)
				if (f == q)
					return true;
		return false;
	}
	
	
	public int[] Deltax_slow(int[] x) {
		return Deltax(this.S, x, 0, x.length);
	}
	
	
	public int[] Deltax(int[] x) {
		return Deltax(this.S, x, 0, x.length, new boolean[this.Q]);
	}
	
	public int[] epsilon_closure(int q) {
		boolean[] found = new boolean[this.Q];
		int[] out = new int[epsilon_closure(q, found)];
		for (int i = 0, n = 0; i < this.Q; i++)
			if (found[i])
				out[n++] = i;
		return out;
	}
	
	private int epsilon_closure(int q, boolean[] found) {
		if (!found[q]) {
			found[q] = true;
			int[] next = Delta(q, 0);
			int n = 1;
			for (int p : next)
				n += epsilon_closure(p, found);
			return n;
		}
		return 0;
	}

	private int[] Deltax(int[] Q, int[] x, int i, int len) {
		if (i == len)
			return Q;
		boolean[] has = new boolean[this.Q];
		int[] out = new int[getSizeOf(Q, i, has, has)];
		fillIn(out, has);
		return Deltax(out, x, i+1, len);
	}

	private int[] Deltax(int[] Q, int[] x, int i, int len, boolean[] found) {
		if (i == len)
			return Q;
		boolean[] has = new boolean[this.Q];
		int[] out = new int[getSizeOf(Q, i, found, has)];
		fillIn(out, has);
		return Deltax(out, x, i+1, len, found);
	}
	
	@SuppressWarnings("null")
	public DFA makeDFA() {
		if (this.dfaConversion != null) {
			return this.dfaConversion;
		} else {
			return computeDFA();
		}
	}
	
	/**
	 * @return
	 */
	private DFA computeDFA() {
		HashMap<IntArr, HashMap<Integer, IntArr>> places = 
				new HashMap<IntArr, HashMap<Integer, IntArr>>();
		IntArr start = new IntArr(this.S);
		makeDFA(start, places);
		Set<IntArr> states = places.keySet();
		HashMap<IntArr, Integer> newStateNum = new HashMap<IntArr, Integer>();
		
		int numStates = states.size();
		int[] finalStates = new int[this.numFinal];
		int[][] delta = new int[numStates][this.Sigma+1];
		
		int i = 0, n = 0;
		for (IntArr a : states) {
			if (a.isFinal)
				finalStates[n++] = i;
			newStateNum.put(a, i++);
		}
		i = 0;
		for (IntArr a : states) {
			int[] dq = delta[newStateNum.get(a)];
			for (int k = 1; k <= this.Sigma; k++) {
				IntArr arr0 = places.get(a).get(k);
//				for (IntArr arr : newStateNum.keySet())
//					if (arr.equals(arr0))
//						dq[k] = newStateNum.get(arr);
				dq[k] = newStateNum.get(arr0);
			}
		}
		
		DFA m = new DFA(numStates, this.Sigma, delta, newStateNum.get(start), finalStates);
		this.dfaConversion = m;
		return m;
	}


	private void makeDFA(IntArr curr, HashMap<IntArr, HashMap<Integer, IntArr>> places) {
		if (!places.containsKey(curr)) {
//			for (IntArr arr : places.keySet())
//				if (arr.equals(curr)) return;
			places.put(curr, new HashMap<Integer, IntArr>());
			if (curr.isFinal)
				this.numFinal++;
			boolean[] has = new boolean[this.Q];
			for (int i = 1; i <= this.Sigma; i++) {
				int[] out = new int[getSizeOf(curr.first, i, has, has)];
				fillIn(out, has);
				IntArr next = new IntArr(out);
				places.get(curr).put(i, next);
				makeDFA(next, places);
			}
		}
	}

	private int getSizeOf(int[] states, int i, boolean[] found, boolean[] has) {
		int n = 0;
		for (int q : states)
			for (int out : Delta(q, i)) {
				if (!found[out]) {
					found[out] = true;
					has[out] = true;
					n++;
				}
				for (int eps : epsilon_closure(out))
					if (!found[out]) {
						found[out] = true;
						has[eps] = true;
						n++;
					}
			}
		return n;
	}
	
	private static void fillIn(int[] out, boolean[] has) {
		for (int k = 0, n = 0; k < has.length; k++)
			if (has[k])
				out[n++] = k;
	}

	private class IntArr {
		final int[] first;
		final boolean isFinal;
				
		private IntArr(int[] first) {
			this.first = first;
			this.isFinal = checkFinal(first);
		}
		
		private boolean checkFinal(int[] first) {
			for (int i : first)
				for (int f : NFA.this.F)
					if (i == f)
						return true;
			return false;
		}

		/* (non-Javadoc)
		 * @see java.lang.Object#equals(java.lang.Object)
		 */
		@SuppressWarnings("null")
		@Override
		public boolean equals(Object o) {
			return (o instanceof IntArr && compare(((IntArr) o).first)) || 
					(o instanceof int[] && compare((int[]) o));
		}
		
		public boolean compare(int[] arr) {
			if (this.first.length != arr.length) return false;
			for (int i = 0; i < this.first.length; i++)
				if (this.first[i] != arr[i])
					return false;
				
			return true;
		}

		@Override
		public int hashCode() {
			return this.first.length;
		}
	}

}
